package com.zjsru.plan2023.oneday;

/**
 * @Author: CookLee
 * @Date: 2023/5/19
 * 活字印刷
 *
 * 输入："AAB"
 * 输出：8
 * 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
 *
 * 输入："AAABBC"
 * 输出：188
 */
public class NumTilePossibilities {
    
    /**
     * 回溯
     *
     * @param tiles 瓷砖
     * @return int
     */
    public int numTilePossibilities(String tiles) {
        int[] nums = new int[26];
        for (char c : tiles.toCharArray()) {
            nums[c - 'A']++;
        }
        return this.dfs(nums);
    }
    
    private int dfs(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0){
                ans++;
                //表示使用了这个字母
                nums[i]--;
                //返回减去上述字母后能搭配的数量
                ans += this.dfs(nums);
                //回溯
                nums[i]++;
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        NumTilePossibilities numTilePossibilities = new NumTilePossibilities();
        String tiles = "AAB";
        System.out.println(numTilePossibilities.numTilePossibilities(tiles));
    }
}
